using System.Linq;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0350. 两个数组的交集 II")]
    public class No0350_Intersect : AbsBaseTestItem
    {
        /*
        给定两个数组，编写一个函数来计算它们的交集。
        说明：
            输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
            我们可以不考虑输出结果的顺序。

        进阶:
            如果给定的数组已经排好序呢？你将如何优化你的算法？
            如果 nums1 的大小比 nums2 小很多，哪种方法更优？
            如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
        */

        public override void OnTest()
        {
            Assert.TestExe(Intersect,
                new int[] { 1, 2, 2, 1 },
                new int[] { 2, 2 },
                new int[] { 2, 2 });

            Assert.TestExe(Intersect,
                new int[] { 4, 9, 5 },
                new int[] { 9, 4, 9, 8, 4 },
                new int[] { 4, 9 },
                new int[] { 9, 4 });
        }

        public int[] Intersect(int[] nums1, int[] nums2)
        {
            if (nums1.Length > nums2.Length)
            {
                return Intersect(nums2, nums1);
            }
            Dictionary<int, int> dic = new Dictionary<int, int>();
            for (int i = 0; i < nums1.Length; i++)
            {
                int key = nums1[i];
                int count = dic.GetValueOrDefault(key, 0) + 1;
                dic[key] = count;
            }
            List<int> result = new List<int>();
            foreach (int num in nums2)
            {
                int count = dic.GetValueOrDefault(num, 0);
                if (count > 0)
                {
                    result.Add(num);
                    count--;
                    dic[num] = count;
                }
            }
            return result.ToArray();
        }
    }
}
